﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;
//32.最长有效括号
//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//怎么判断格式正确？使用一个map，key  =（ val=）
public class Solution32
{
    public int LongestValidParentheses2(string s)//这个情况遇到，））））））（这种情况没法判断
    {

        int len = s.Length;
        if (len < 2)//0个或者1个元素，肯定不匹配
        {
            return 0;
        }


        //找出状态转移方程
        //当前子串是符合的，前面的子串肯定也要符合
        //dp[i]是以index=i结尾的最长子串的长度
        //判断条件是，当前字符是（还是）
        int[] dp = new int[s.Length];
        dp[0] = 0;



        int max = 0;

        for (int i = 1; i < s.Length; i++)
        {


            if (s[i] == '(')//判断前面是不是），是的话+1，不是的话重新计算
            {
                if (s[i - 1] == ')')
                {

                    dp[i] = dp[i - 1] + 1;
                }
                else
                {
                    dp[i] = 1;
                }

            }
            else
            {
                //(s[i] == ')'),判断前面是不是（，是的话+1，不是的话忽略

                if (s[i - 1] == '(')
                {

                    dp[i] = dp[i - 1] + 1;
                }
                else
                {
                    dp[i] = 0;
                }
            }
            max = Math.Max(max, dp[i]);
        }

        return max;
    }
    public int LongestValidParentheses3(string s)//动态规划，优化
    {

        int len = s.Length;
        if (len < 2)//0个或者1个元素，肯定不匹配
        {
            return 0;
        }


        //找出状态转移方程
        //当前子串是符合的，前面的子串肯定也要符合
        //dp[i]是以index=i结尾的最长子串的长度
        //判断条件是，当前字符是（还是）
        int[] dp = new int[s.Length];
        dp[0] = 0;



        int max = 0;

        //每两个字符检测一次，这个字符必须是）
        //这两个字符的情况有四种
        //有效两种
        //  情况 1, ()
        //  情况 2, ))
        //无效两种
        //  情况 3, ((
        //  情况 4, )(
        for (int i = 1; i < s.Length; i++)
        {


            if (s[i] == '(')//以这个结尾的，一定无效
            {

                //dp[i] = 0;


            }
            else
            {
                //(s[i] == ')'),判断前面是不是（，是的话+1，不是的话忽略

                if (s[i - 1] == '(')//     情况 1, ()
                {
                    if(i < 2){//i=1,越界，直接为2
                        dp[i] =  2;
                    }
                    else
                    {
                        dp[i] = dp[i - 2] + 2;
                    }


                }
                else//  情况 2, ))，这种情况，先看dp[i-1]是不是有效子串，是的话，dp[i-1]子串之前是不是可以匹配的（
                {//也就是s[i-dp[i-1]-1]=='(',这个时候子串长度加上'('之前的长度dp[i - dp[i - 1] - 2]

                    if ((i - dp[i - 1] - 1)>=0)
                    {
                        if (s[i - dp[i - 1] - 1] == '(')
                        {
                            if ((i - dp[i - 1] - 2) > 0)
                            {
                                dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;

                            }
                            else
                            {
                                dp[i] = dp[i - 1] + 2;
                            }
                            //2是最后一个）匹配的，dp[i - 1]是倒数第二个）匹配的，dp[i - dp[i - 1] - 2]是倒数第二个）匹配的（之前的长度
                        }
                    }
                    else
                    {
                        //也就是s[i - dp[i - 1] - 1]越界，说明没有有效子串
                    }



                }
            }
            max = Math.Max(max, dp[i]);
        }

        return max;
    }

    public int LongestValidParentheses(string s)//使用栈
    {
        int len = s.Length;
        if (len < 2)//0个或者1个元素，肯定不匹配
        {
            return 0;
        }

        Stack<int> index = new Stack<int>();
        index.Push(-1);//不设置这个初始值，开头是")()())"的时候会报错stack空
        int preindex = 0;
        int curlenth = 0;
        int maxlenth = 0;
        for (int i = 0; i < s.Length; i++)
        {

            if (s[i] == '(')
            {//入栈
                index.Push(i);
            }
            else//出栈
            {
                preindex = index.Pop();//先出栈，因为栈里面只有'('//栈顶的(弹出
                if (index.Count > 0)
                {
                    
                    curlenth = i - index.Peek();//计算一次有效长度


                }
                else
                { //栈空，入栈
                    index.Push(i);
                }

                maxlenth = Math.Max(maxlenth, curlenth);

            }
        }
        return maxlenth;
    }
}

class Program32
{
    static void Main32(string[] args)
    {


        //string s = "(()";
        string s = ")))))))(";
        //string s = ")()())";
        //string s = "())((())";
        Solution32 solution = new();
        int res = solution.LongestValidParentheses(s);
        Console.WriteLine("最长有效括号子串长度：" + res);

    }


}